import collections
from typing import List


class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        from collections import Counter
        counts = Counter(nums)
        return max(counts, key=counts.get)

    def majorityElement1(self, nums: List[int]) -> int:
        n = len(nums)
        i = 0
        nums_dict = {}
        while i < n:
            if nums[i] in nums_dict:
                nums_dict[nums[i]] += 1
            else:
                nums_dict[nums[i]] = 1
            i += 1
        return max(nums_dict.keys(), key=nums_dict.get)

    # 排序
    def majorityElement2(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums) // 2]

    # 随机化
    def majorityElement3(self, nums: List[int]) -> int:
        import random
        majority_count = len(nums) // 2

        while True:
            candidate = random.choice(nums)
            if sum(1 for elem in nums if elem == candidate) > majority_count:
                return candidate

    # 分治法
    # 思路：如果数 a 是数组 nums 的众数，如果我们将 nums 分成两部分，那么 a 必定是至少一部分的众数。
    def majorityElement4(self, nums: List[int]) -> int:
        def majority_element_rec(lo, hi) -> int:
            # base case; the only element in an array of size 1 is the majority
            # element.
            if lo == hi:
                return nums[lo]

            # recurse on left and right halves of this slice.
            mid = (hi - lo) // 2 + lo
            left = majority_element_rec(lo, mid)
            right = majority_element_rec(mid + 1, hi)

            # if the two halves agree on the majority element, return it.
            if left == right:
                return left

            # otherwise, count each element and return the "winner".
            left_count = sum(1 for i in range(lo, hi + 1) if nums[i] == left)
            right_count = sum(1 for i in range(lo, hi + 1) if nums[i] == right)

            return left if left_count > right_count else right

        return majority_element_rec(0, len(nums) - 1)

    # Boyer-Moore投票算法
    def majorityElement5(self, nums: List[int]) -> int:
        count = 0
        candidate = None

        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)

        return candidate


def fibonacciSequence(n):
    if n == 1:
        return 1
    if n == 2:
        return 1
    return fibonacciSequence(n - 1) + fibonacciSequence(n - 2)


if __name__ == '__main__':
    nums = [2, 2, 1, 1, 1]
    s = Solution()
    # print(fibonacciSequence(0))
    print(s.majorityElement(nums))
